package com.liunian.algorithmstudy.tree;

public class CountNodes222 extends TreeNode {
	public int countNodes(TreeNode root) {
		if (root == null) {
			return 0;
		}
		TreeNode left1 = root.left;
		TreeNode right1 = root.right;
		int leftHeight = 0;
		int rightHeight = 0;
		while (left1 != null) {
			left1 = left1.left;
			leftHeight++;
		}
		while (right1 != null) {
			right1 = right1.right;
			rightHeight++;
		}
		if (leftHeight == rightHeight) {
			return (2 << leftHeight) - 1;
		}
		int l = countNodes(root.left);
		int r = countNodes(root.right);
		return l + r + 1;
	}

	public static void main(String[] args) {
		TreeNode treeNode4 = new TreeNode(4, null, null);
		TreeNode treeNode5 = new TreeNode(5, null, null);
		TreeNode treeNode6 = new TreeNode(6, null, null);
		TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);
		TreeNode treeNode3 = new TreeNode(3, treeNode6, null);
		TreeNode treeNode1 = new TreeNode(1, treeNode2, treeNode3);
		CountNodes222 count = new CountNodes222();
		System.out.println(count.countNodes(treeNode1));
	}

}
